import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/*
 * @lc app=leetcode.cn id=131 lang=java
 *
 * [131] 分割回文串
 */

// @lc code=start
class Solution {
    boolean[][] f;//存放i,j直接能否组成回文串，true为可以。
    List<List<String>> ret =  new ArrayList<>();
    List<String> ans = new ArrayList<>();
    int n;
    public List<List<String>> partition(String s) {
        n = s.length();
        f = new boolean[n][n];
        for(int i = 0;i<n;i++){
            Arrays.fill(f[i], true);
        }

        for(int i = n-1 ;i>=0;i--){
            for(int j = i+1 ;j<n ;j++){
                f[i][j] = (s.charAt(i)==s.charAt(j) && f[i+1][j-1] );//动态规划
            }
        }

        dfs(s,0);
        return ret;
    }

    void dfs(String s, int index){
        if(index == n){//代表dfs到最后一个字符n-1了，再加1变成n的。
            ret.add(new ArrayList<>(ans));//返回ans的复制
            // ret.add(ans);//直接返回ans不行，因为ans会被清空，导致ret内的内容也被清空。
            return;
        }

        for(int j=index ;j<n ;j++){
            if(f[index][j]){
                ans.add(s.substring(index,j+1));//截取index,j之间的作为答案
                dfs(s, j+1);//找下一个回文串
                ans.remove(ans.size()-1);//回溯法，去掉最近的一个添加结果
                // 并且如果找到结果后这一步回溯会把ans清空，不用手动清空
            }
        }
    }
}
// @lc code=end

